package ai.zixing.mashibing.basic_class.class04;

// 大根堆
public class Code02_Heap01 {

    public static class MyMaxHeap{
        private int[] heap;
        // 堆的大小
        private final int limit;
        private int heapSize;

        public MyMaxHeap(int limit) {
            this.limit = limit;
            heap = new int[limit];
            heapSize = 0;
        }

        public boolean isEmpty() {
            return heapSize == 0;
        }

        public boolean isFull() {
            return heapSize == limit;
        }

        public void push(int value) {
            if (heapSize == limit) {
                throw new RuntimeException("heap is full");
            }
            heap[heapSize] = value;
            // 调整堆结构为大根堆
            heapInsert(heap, heapSize++);
        }

        // 调整顺序，保证大根堆
        private void heapInsert(int[] arr, int index) {
            // (index - 1) / 2 是 index 的父节点
            while (arr[index] > arr[(index - 1) / 2]) {
                // 如果当前节点大于父节点，需要交换
                swap(arr, index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        // 大根堆弹出的是最大值
        public int pop() {
            int ans = heap[0];
            // 弹出之后需要调整堆
            // 将最后一个调整到heap的首位置
            swap(heap, 0, --heapSize);
            // 调整堆顶为最大的元素
            heapIfy(heap, 0, heapSize);
            return ans;
        }

        // 从 index 位置，往下看，不断下沉
        // 停止：我的孩子都不在比我大；已经没有孩子
        // O(logN)
        private void heapIfy(int[] arr, int index, int heapSize) {
            // 左孩子下标 index * 2 + 1
            int left = index * 2 + 1;
            // 左孩子不越界
            while (left < heapSize) {
                // 有右孩子，且右孩子值大于左孩子值
                int maxIndex = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
                maxIndex = arr[index] > arr[maxIndex] ? index : maxIndex;
                // 自己就是最大则跳出
                if (maxIndex == index) {
                    break;
                }
                swap(arr, index, maxIndex);
                index = maxIndex;
                left = index * 2 + 1;
            }
        }

        private void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    public static class RightMaxHeap{
        private int[] arr;
        private final int limit;
        private int size;

        public RightMaxHeap(int limit) {
            this.limit = limit;
            size = 0;
            arr = new int[limit];
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public boolean isFull() {
            return size == limit;
        }

        public void push(int value) {
            if (size == limit) {
                throw new RuntimeException("heap is full");
            }
            arr[size++] = value;
        }

        public int pop() {
            int maxIndex = 0;
            for (int i = 0; i < size; i++) {
                if (arr[i] > arr[maxIndex]) {
                    maxIndex = i;
                }
            }
            int ans = arr[maxIndex];
            arr[maxIndex] = arr[--size];
            return ans;
        }
    }

    public static void main(String[] args) {
        int value = 100;
        int limit = 10;
        int testTimes = 20;
        for (int i = 0; i < testTimes; i++) {
            int curLimit = (int) (Math.random() * limit);
            MyMaxHeap my = new MyMaxHeap(curLimit);
            RightMaxHeap test = new RightMaxHeap(curLimit);
            int curOpTimes = (int) (Math.random() * limit);
            for (int j = 0; j < curOpTimes; j++) {
                if (my.isEmpty() != test.isEmpty()) {
                    System.out.println("Oops!");
                }
                if (my.isFull() != test.isFull()) {
                    System.out.println("Oops!");
                }
                if (my.isEmpty()) {
                    int curValue = (int) (Math.random() * value);
                    my.push(curValue);
                    test.push(curValue);
                } else if (my.isFull()) {
                    if (my.pop() != test.pop()) {
                        printArr(test.arr);
                        System.out.println("Oops!");
                    }
                } else {
                    if (Math.random() < 0.5) {
                        int curValue = (int) (Math.random() * value);
                        my.push(curValue);
                        test.push(curValue);
                    } else {
                        if (my.pop() != test.pop()) {
                            System.out.println("Oops!");
                        }
                    }
                }
            }
        }
    }

    public static void printArr(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}
